package com.ctrip.study.algorithm.pratice;

import junit.framework.TestCase;

/**
 * 题目：输入一个已经按升序排序过的数组和一个数字，
   在数组中查找两个数，使得它们的和正好是输入的那个数字。
   要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
   例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。.
 */
public class SearchArraySum extends TestCase{
	
	public void test(){
		int[] array = {1,2,4,7,11,15};
		int sum = 15;
		search(array, sum);
	}

	/**
	 *  解题思路：设置头尾两个指针，从第一个元素和最后一个
	 *  元素相加，如果大于sum,则尾指针向前移1个元素，继续判断两个数的和；
 	 *	如果小于sum，则头指针向后移1个元素，继续判断两个数的和.
	 */
	private void search(int[] array, int sum) {
		int head = 0;
		int tail = array.length - 1;
		while(head < tail){
			if(array[head] + array[tail] > sum){
				tail--;
			}else if(array[head] + array[tail] < sum){
				head++;
			}else{
				break;
			}
		}
		System.out.println(array[head] + "----" + array[tail]);
	}
	

}
